//题目:
// 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
// 这个岛被分割成一个由若干方形单元格组成的网格。
// 给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标(r, c)上单元格高于海平面的高度 。
// 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。
// 水可以从海洋附近的任何单元格流入海洋。
// 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码:
class Solution 
{
    //暴搜超时
//     bool pflag=false,aflag=false;
//     vector<vector<bool>> flag;
//     int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
public:
//     bool dfs(vector<vector<int>>& heights,int row,int col)
//     {
//         flag[row][col]=true;
//         if(row==0 || col==0)pflag=true;
//         if(row==heights.size()-1 || col==heights[0].size()-1)aflag=true;
//         if(pflag==true && aflag==true)return true;

//         for(int i=0;i<4;i++)
//         {
//             int x=row+dx[i],y=col+dy[i];
//             if(x>=0 && x<heights.size() && y>=0 && y<heights[0].size() && flag[x][y]==false && heights[x][y]<=heights[row][col])
//             {
//                 flag[x][y]=true;
//                 if(dfs(heights,x,y)==true)return true;
//             }
//         }

//         return false;
//     }
//     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
//     {
//         vector<vector<int>> ret;
//         flag=vector<vector<bool>>(heights.size(),vector<bool>(heights[0].size(),false));

//         for(int i=0;i<heights.size();i++)
//         {
//             for(int j=0;j<heights[0].size();j++)
//             {
//                 if(dfs(heights,i,j)==true)ret.push_back({i,j});
//                 pflag=false,aflag=false;
//                 flag=vector<vector<bool>>(heights.size(),vector<bool>(heights[0].size(),false));     
//             }
//         }
//         return ret;
//     }

    vector<vector<int>> ret;
    set<pair<int,int>> vp,va;//存放太平洋、大西洋的水分别可以逆流向那些位置
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    bool pflag[200][200]={false},aflag[200][200]={false};
    
    void p_dfs(vector<vector<int>>& heights,int row,int col)
    {
        vp.insert({row,col});
        if(va.count({row,col}))ret.push_back({row,col});
        pflag[row][col]=true;

        for(int i=0;i<4;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<heights.size() && y>=0 && y<heights[0].size() && pflag[x][y]==false && heights[x][y]>=heights[row][col])
                p_dfs(heights,x,y);
        }
    }
    void a_dfs(vector<vector<int>>& heights,int row,int col)
    {
        va.insert({row,col});
        if(vp.count({row,col}))ret.push_back({row,col});
        aflag[row][col]=true;

        for(int i=0;i<4;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<heights.size() && y>=0 && y<heights[0].size() && aflag[x][y]==false && heights[x][y]>=heights[row][col])
                a_dfs(heights,x,y);
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
    {
        for(int i=0;i<heights.size();i++)
        {
            if(pflag[i][0]==false) p_dfs(heights,i,0);
            if(aflag[i][heights[0].size()-1]==false) a_dfs(heights,i,heights[0].size()-1);
        }
        for(int i=0;i<heights[0].size();i++)
        {
            if(pflag[0][i]==false) p_dfs(heights,0,i);
            if(aflag[heights.size()-1][i]==false) a_dfs(heights,heights.size()-1,i);
        }
        return ret;
    }
};